{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Delete N Nodes After M Nodes of a Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: deleteNodes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除链表 M 个节点之后的 N 个节点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定链表&nbsp;<code>head</code>&nbsp;和两个整数&nbsp;<code>m</code>&nbsp;和&nbsp;<code>n</code>. 遍历该链表并按照如下方式删除节点:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>开始时以头节点作为当前节点.</li>\n",
    "\t<li>保留以当前节点开始的前&nbsp;<code>m</code>&nbsp;个节点.</li>\n",
    "\t<li>删除接下来的&nbsp;<code>n</code>&nbsp;个节点.</li>\n",
    "\t<li>重复步骤 2 和 3,&nbsp;直到到达链表结尾.</li>\n",
    "</ul>\n",
    "\n",
    "<p>在删除了指定结点之后,&nbsp;返回修改过后的链表的头节点.</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/06/sample_1_1848.png\" style=\"height: 95px; width: 620px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3\n",
    "<strong>输出:</strong> [1,2,6,7,11,12]\n",
    "<strong>解析: </strong>保留前(m = 2)个结点,  也就是以黑色节点表示的从链表头结点开始的结点(1 -&gt;2).\n",
    "删除接下来的(n = 3)个结点(3 -&gt; 4 -&gt; 5), 在图中以红色结点表示.\n",
    "继续相同的操作, 直到链表的末尾.\n",
    "返回删除结点之后的链表的头结点.</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/06/06/sample_2_1848.png\" style=\"height: 123px; width: 620px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3\n",
    "<strong>输出:</strong> [1,5,9]\n",
    "<strong>解析:</strong> 返回删除结点之后的链表的头结点.</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [1,2,3,4,5,6,7,8,9,10,11], m = 3, n = 1\n",
    "<strong>输出:</strong> [1,2,3,5,6,7,9,10,11]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;4:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [9,3,7,7,9,10,8,2], m = 1, n = 2\n",
    "<strong>输出:</strong> [9,7,8]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>链表中节点数目在范围 <code>[1, 10<sup>4</sup>]</code> 内</li>\n",
    "\t<li><code>1 &lt;= Node.val &lt;= 10<sup>6</sup></code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶:</strong> 你能通过<strong> 就地 </strong>修改链表的方式解决这个问题吗?</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [delete-n-nodes-after-m-nodes-of-a-linked-list](https://leetcode.cn/problems/delete-n-nodes-after-m-nodes-of-a-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [delete-n-nodes-after-m-nodes-of-a-linked-list](https://leetcode.cn/problems/delete-n-nodes-after-m-nodes-of-a-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5,6,7,8,9,10,11,12,13]\\n2\\n3', '[1,2,3,4,5,6,7,8,9,10,11]\\n1\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur_node = head\n",
    "        while cur_node:\n",
    "            for i in range(m-1):\n",
    "                if cur_node:\n",
    "                    cur_node = cur_node.next\n",
    "                else:\n",
    "                    return head\n",
    "            if cur_node:\n",
    "                step_node = cur_node.next\n",
    "            else:\n",
    "                return head\n",
    "            for j in range(n):\n",
    "                if step_node:\n",
    "                    step_node = step_node.next\n",
    "                else:\n",
    "                    cur_node.next = step_node\n",
    "                    return head\n",
    "            cur_node.next = step_node\n",
    "            cur_node = step_node\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        return self.answer_1(head, m, n)\n",
    "\n",
    "    def answer_1(self, head, m, n):\n",
    "        curr = head\n",
    "        last = head\n",
    "\n",
    "        while curr:\n",
    "            p , q = m, n\n",
    "            while p  and curr:\n",
    "                last = curr\n",
    "                curr = curr.next\n",
    "                p -= 1\n",
    "\n",
    "            while q and curr:\n",
    "                curr = curr.next\n",
    "                q -= 1\n",
    "            last.next = curr\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        tail = head\n",
    "\n",
    "        while cur:\n",
    "            mc = m\n",
    "            nc = n\n",
    "            while cur and mc > 0:\n",
    "                tail = cur\n",
    "                cur = cur.next\n",
    "                mc -= 1\n",
    "            while cur and nc > 0:\n",
    "                nc -= 1\n",
    "                cur = cur.next\n",
    "            tail.next = cur\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur_node = head\n",
    "        ctr = 1\n",
    "        \n",
    "        while True:\n",
    "            while cur_node and ctr < m:\n",
    "                cur_node = cur_node.next\n",
    "                ctr += 1\n",
    "            \n",
    "            if not cur_node:\n",
    "                return head\n",
    "            \n",
    "            del_ctr = 0\n",
    "            del_node = cur_node\n",
    "            while del_node and del_ctr < n:\n",
    "                del_node = del_node.next\n",
    "                del_ctr += 1\n",
    "            \n",
    "            if not del_node:\n",
    "                cur_node.next = None\n",
    "            else:\n",
    "                cur_node.next = del_node.next\n",
    "                ctr = 1\n",
    "            cur_node = cur_node.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        \n",
    "        p=head\n",
    "\n",
    "        while p:\n",
    "\n",
    "            t=1\n",
    "            while p and t<m:\n",
    "                t+=1\n",
    "                p=p.next\n",
    "            q=p\n",
    "            if p:\n",
    "                t=0\n",
    "                while q and t<=n:\n",
    "                    q=q.next\n",
    "                    t+=1\n",
    "                p.next=q\n",
    "                p=p.next\n",
    "        return head\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head \n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n \n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next \n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return\n",
    "        left, right = head, head\n",
    "        idx = -1\n",
    "        while right != None:\n",
    "            idx += 1\n",
    "            cur = idx % (m+n)\n",
    "            # print(left.val, right.val, cur)\n",
    "            if cur < m-1:\n",
    "                left = left.next\n",
    "                right = right.next\n",
    "            elif n+m-1>=cur >= m-1:\n",
    "                left.next = right.next\n",
    "                right = right.next\n",
    "                if cur == n+m-1:\n",
    "                    left = right\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode()\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            q,p = m,n\n",
    "            while cur.next and q>0:\n",
    "                cur = cur.next\n",
    "                q -=1\n",
    "            while cur.next and p>0:\n",
    "                p-=1\n",
    "                cur.next = cur.next.next\n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        point=head\n",
    "        while point:\n",
    "            try:\n",
    "                for i in range(1,m):\n",
    "                    point=point.next\n",
    "                for j in range(n):\n",
    "                    point.next=point.next.next\n",
    "                point=point.next\n",
    "            except:\n",
    "                return head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        low = head\n",
    "        high = head\n",
    "        \n",
    "        while True:\n",
    "            for _ in range(m-1):\n",
    "                if low.next:\n",
    "                    low = low.next\n",
    "                else:\n",
    "                    return head\n",
    "\n",
    "            for _ in range(m+n):\n",
    "                if high.next:\n",
    "                    high = high.next\n",
    "                else:\n",
    "                    low.next = None\n",
    "                    return head\n",
    "        \n",
    "            low.next = high\n",
    "            low = high"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur != None:\n",
    "            i = 0\n",
    "            while cur != None and i < m-1:\n",
    "                cur = cur.next\n",
    "                i += 1\n",
    "            pos = cur\n",
    "            if pos == None:\n",
    "                return head\n",
    "            i = 0\n",
    "            cur = cur.next\n",
    "            while cur != None and i < n:\n",
    "                pos.next = cur.next\n",
    "                cur = cur.next\n",
    "                i += 1\n",
    "        return head\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        p = head\n",
    "        q = head\n",
    "        while p:\n",
    "            m1 = n1 = 0\n",
    "            while m1<m-1 and p:\n",
    "                p = p.next\n",
    "                m1+=1\n",
    "            if not p:\n",
    "                break\n",
    "            q = p\n",
    "            while n1 < n and q:\n",
    "                q = q.next\n",
    "                n1 += 1\n",
    "            if  q:\n",
    "                p.next = q.next\n",
    "            else:\n",
    "                p.next = None\n",
    "            p = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        tmp = ListNode(next = head)\n",
    "        while tmp.next != None:\n",
    "            for i in range(m):\n",
    "                tmp = tmp.next\n",
    "                if tmp == None:\n",
    "                    break\n",
    "            if tmp == None or tmp.next == None:\n",
    "                break\n",
    "\n",
    "            for i in range(n):\n",
    "                if tmp.next == None:\n",
    "                    break\n",
    "                tmp.next = tmp.next.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    return head\n",
    "\n",
    "            if cur:\n",
    "                kk = cur.next\n",
    "            else:\n",
    "                return head\n",
    "            \n",
    "            for j in range(n):\n",
    "                if kk:\n",
    "                    kk = kk.next\n",
    "                else:\n",
    "                    cur.next = kk\n",
    "                    return head\n",
    "            \n",
    "            cur.next = kk\n",
    "            cur = kk\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        curNode = head\n",
    "\n",
    "        while next != None:\n",
    "            for i in range(m-1):\n",
    "                if curNode:\n",
    "                    curNode = curNode.next\n",
    "                \n",
    "            if not curNode:\n",
    "                break\n",
    "\n",
    "            for j in range(n):\n",
    "                if curNode.next:\n",
    "                    curNode.next = curNode.next.next\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            curNode = curNode.next\n",
    "            \n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        node = head\n",
    "        while True:\n",
    "            i = 0\n",
    "            while node is not None and i < m - 1:\n",
    "                # 经过m个节点\n",
    "                node = node.next\n",
    "                i += 1\n",
    "            if node is None:\n",
    "                break\n",
    "            pre = node\n",
    "            while node is not None and i < m + n:\n",
    "                node = node.next\n",
    "                i += 1\n",
    "            if pre is not None:\n",
    "                pre.next = node\n",
    "            if pre is None or node is None:\n",
    "                break\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        a=b=head\n",
    "        c,d=m,n\n",
    "        while m-1 and a.next:\n",
    "            a,b=a.next,b.next\n",
    "            m-=1\n",
    "        while n and b.next:\n",
    "            b=b.next\n",
    "            n-=1\n",
    "        a.next=self.deleteNodes(b.next, c, d)\n",
    "        return head\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        while cur:\n",
    "            for _ in range(m - 1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    return head\n",
    "            if cur:\n",
    "                tmp = cur.next\n",
    "            else:\n",
    "                return head\n",
    "            \n",
    "            for _ in range(n):\n",
    "                if tmp:\n",
    "                    tmp = tmp.next\n",
    "                else:\n",
    "                    cur.next = tmp\n",
    "                    return head\n",
    "            cur.next = tmp\n",
    "            cur = tmp\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        # m + n，每 m + n个节点中，保留前m个，删去后n个\n",
    "        cur = head\n",
    "        tmp = 1\n",
    "        while cur and cur.next:\n",
    "            if tmp < m:\n",
    "                cur = cur.next\n",
    "            else:\n",
    "                cur.next = cur.next.next\n",
    "            tmp = (tmp + 1) % (m + n)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        end = False\n",
    "        while not end:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    end = True\n",
    "                    break\n",
    "            if end:\n",
    "                break\n",
    "            if not cur:\n",
    "                break\n",
    "            last = cur\n",
    "            for i in range(n+1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "                else:\n",
    "                    end = True\n",
    "                    break\n",
    "            last.next = cur\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        prehead = ListNode(0,head)\n",
    "        i = 1\n",
    "        while head and i<m:\n",
    "            head = head.next\n",
    "            i+=1\n",
    "        if not head:\n",
    "            return prehead.next\n",
    "        tmp = head.next\n",
    "        i = 0\n",
    "        while tmp and i<n:\n",
    "            tmp = tmp.next\n",
    "            i+=1\n",
    "        head.next = tmp\n",
    "        if tmp:\n",
    "            head.next = self.deleteNodes(tmp,m,n)\n",
    "        return prehead.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)#创建一个dummy指针\n",
    "        dummy.next = head#dummy的next指向head\n",
    "        cur = dummy#现任节点\n",
    "\n",
    "        while (cur):#cur == None时退出while循环\n",
    "            for i in range(0, m):#从dummy开始，往前找m个位置，个数不足m个, 终止循环返回结果\n",
    "                if (cur == None) : \n",
    "                    break\n",
    "                cur = cur.next#现任节点进行右移\n",
    "\n",
    "            if (cur == None) :\n",
    "                break\n",
    "            for i in range(0, n):\n",
    "                if (cur.next == None) :\n",
    "                    break; #往前找n个位置，个数不足n个, 终止循环返回结果\n",
    "                cur.next = cur.next.next#现任节点next指向cur.next.next节点，则删除了后一节点\n",
    "\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        \n",
    "        curr = head\n",
    "        while curr:\n",
    "            count = 1\n",
    "            while curr and count < m:\n",
    "                curr = curr.next\n",
    "                count += 1\n",
    "            \n",
    "            if not curr:\n",
    "                break\n",
    "            \n",
    "            res = n\n",
    "            while curr.next and res > 0:\n",
    "                curr.next = curr.next.next\n",
    "                res -= 1\n",
    "            \n",
    "            curr = curr.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head \n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n \n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next \n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head \n",
    "        cur = dummy \n",
    "        while(cur):\n",
    "            for i in range(m):\n",
    "                if(cur == None):\n",
    "                    break  \n",
    "                cur = cur.next \n",
    "            if(cur == None):\n",
    "                break \n",
    "            for i in range(n):\n",
    "                if(cur.next == None):\n",
    "                    break \n",
    "                cur.next = cur.next.next \n",
    "        return head\n",
    "        # dummy = ListNode(-1)\n",
    "        # dummy.next = head\n",
    "        # cur = dummy\n",
    "        # while (cur):\n",
    "        #     for i in range(0, m):\n",
    "        #         if (cur == None) : # less than m elements left, break\n",
    "        #             break\n",
    "        #         cur = cur.next\n",
    "\n",
    "        #     if (cur == None) :\n",
    "        #         break\n",
    "        #     for i in range(0, n):\n",
    "        #         if (cur.next == None) :\n",
    "        #             break; # nothing left to be deleted\n",
    "        #         # next =cur.next\n",
    "        #         cur.next = cur.next.next\n",
    "\n",
    "        # return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head \n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n \n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next \n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while (cur):\n",
    "            for i in range(0, m):\n",
    "                if (cur == None) : # less than m elements left, break\n",
    "                    break\n",
    "                cur = cur.next\n",
    "\n",
    "            if (cur == None) :\n",
    "                break\n",
    "            for i in range(0, n):\n",
    "                if (cur.next == None) :\n",
    "                    break; # nothing left to be deleted\n",
    "                next =cur.next\n",
    "                cur.next = cur.next.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "\n",
    "        while True:\n",
    "            i, j = m - 1, n + 1\n",
    "            while cur and i:\n",
    "                cur = cur.next\n",
    "                i -= 1\n",
    "            nxt = cur\n",
    "            while nxt and j:\n",
    "                nxt = nxt.next\n",
    "                j -= 1\n",
    "            if not cur:\n",
    "                return head\n",
    "            cur.next = nxt\n",
    "            cur = nxt\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        p = head\n",
    "        cnt = 1\n",
    "        while p:\n",
    "            if cnt == m:\n",
    "                q = p\n",
    "                while cnt < m+n and q.next:\n",
    "                    q = q.next\n",
    "                    cnt += 1\n",
    "                p.next = q.next\n",
    "                p = q.next\n",
    "                cnt = 1\n",
    "            else:\n",
    "                p = p.next\n",
    "                cnt += 1\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        index = head\n",
    "        \n",
    "        while index != None:\n",
    "            cm = m\n",
    "            cn = n\n",
    "            while cm > 0:\n",
    "                if index != None:\n",
    "                    cm -= 1\n",
    "                    temp = index\n",
    "                    index = index.next\n",
    "                else: break\n",
    "                    \n",
    "            while cn > 0:\n",
    "                if index != None:\n",
    "                    cn -= 1\n",
    "                    index = index.next\n",
    "                    temp.next = index\n",
    "                else: break\n",
    "        \n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur=head\n",
    "        while cur:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur=cur.next\n",
    "                else:\n",
    "                    return head\n",
    "            if cur:\n",
    "                kk=cur.next\n",
    "            else:\n",
    "                return head\n",
    "            for j in range(n):\n",
    "                if kk:\n",
    "                    kk=kk.next\n",
    "                else:\n",
    "                    cur.next=kk\n",
    "                    return head\n",
    "            cur.next=kk\n",
    "            cur=kk\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n\n",
    "            while p>0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next\n",
    "            while q>0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        return dummy.next\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        count = 1\n",
    "        pre = cur = head\n",
    "        while cur:\n",
    "            while cur and (0 < count % (m + n) <= m):\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "                count += 1\n",
    "            while cur and (count % (m + n) > m or count % (m + n) == 0):\n",
    "                cur = cur.next\n",
    "                count += 1\n",
    "            pre.next = cur\n",
    "\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p,q = m,n\n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next\n",
    "            while q > 0 and cur.next:     \n",
    "                q -= 1\n",
    "                cur.next = cur.next.next   # 直接改变cur的后继结点。\n",
    "\n",
    "        return dummy.next\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        pred_head = ListNode(-1, head)\n",
    "        node_pre = pred_head\n",
    "        nxt_node = pred_head\n",
    "        while node_pre:\n",
    "            idx_m, idx_n = m, n\n",
    "            for i in range(m):\n",
    "                if not node_pre:\n",
    "                    break\n",
    "                if not node_pre:\n",
    "                    break\n",
    "                node_pre = node_pre.next\n",
    "            for j in range(n):\n",
    "                if not node_pre or not node_pre.next:\n",
    "                    break\n",
    "                node_pre.next = node_pre.next.next\n",
    "\n",
    "        return pred_head.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p, q = m, n\n",
    "            while p > 0 and cur.next:\n",
    "                p -= 1\n",
    "                cur = cur.next\n",
    "            while q > 0 and cur.next:\n",
    "                q -= 1\n",
    "                cur.next = cur.next.next\n",
    "        \n",
    "        return dummy.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "\n",
    "        while cur:\n",
    "            for _ in range(m - 1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "            if not cur:\n",
    "                break\n",
    "            prev = cur\n",
    "            for _ in range(n + 1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "            prev.next = cur\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cnt = -1\n",
    "        cur = dummy = ListNode(-1, head)\n",
    "        while cur:\n",
    "            cur = cur.next\n",
    "            cnt = (cnt + 1) % (m + n)\n",
    "            if cnt < m:\n",
    "                dummy.next = cur\n",
    "                dummy = cur\n",
    "            else:\n",
    "                continue\n",
    "        if dummy: dummy.next = None\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        pre = head\n",
    "        while True:\n",
    "            for _ in range(m-1):\n",
    "                if pre:\n",
    "                    pre = pre.next\n",
    "            \n",
    "            cur = pre\n",
    "            for _ in range(n+1):\n",
    "                if cur:\n",
    "                    cur = cur.next\n",
    "            if pre:\n",
    "                pre.next = cur\n",
    "                pre = cur\n",
    "            else:\n",
    "                break\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        left, right = head, head\n",
    "        remain = 1\n",
    "        remove = 0\n",
    "        while left and right:\n",
    "            if remain < m:\n",
    "                left = left.next\n",
    "                right = right.next\n",
    "                remain += 1\n",
    "            else:\n",
    "                remain = 0\n",
    "                while remove <= n and right:\n",
    "                    right = right.next\n",
    "                    remove += 1\n",
    "                left.next = right\n",
    "                remove = 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head\n",
    "        pre = None\n",
    "        while cur:\n",
    "            count_m = 0\n",
    "            while count_m < m and cur:\n",
    "                pre = cur\n",
    "                cur = cur.next\n",
    "                count_m += 1\n",
    "            count_n = 0\n",
    "            while count_n < n and cur:\n",
    "                cur = cur.next\n",
    "                pre.next = cur\n",
    "                count_n += 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while (cur):\n",
    "            for i in range(0, m):\n",
    "                if (cur == None) : # less than m elements left, break\n",
    "                    break\n",
    "                cur = cur.next\n",
    "\n",
    "            if (cur == None) :\n",
    "                break\n",
    "            for i in range(0, n):\n",
    "                if (cur.next == None) :\n",
    "                    break; # nothing left to be deleted\n",
    "                # next =cur.next\n",
    "                cur.next = cur.next.next\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(0)\n",
    "        dummy.next = head\n",
    "        cur = dummy\n",
    "        while cur.next:\n",
    "            p,q = m,n\n",
    "            while p and cur.next:\n",
    "                cur = cur.next\n",
    "                p-=1\n",
    "            while q and cur.next:\n",
    "                cur.next = cur.next.next\n",
    "                q-=1\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummpy = ListNode(0)\n",
    "        dummpy.next = head\n",
    "        cur = dummpy\n",
    "\n",
    "        while cur.next:\n",
    "            for i in range(m):\n",
    "                if cur.next:\n",
    "                    cur = cur.next\n",
    "            for i in range(n):\n",
    "                if cur.next:\n",
    "                    cur.next = cur.next.next\n",
    "\n",
    "        return dummpy.next\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        low = high = head\n",
    "        while True:\n",
    "            for _ in range(m -1):\n",
    "                if low.next: low = low.next\n",
    "                else: return head\n",
    "            for _ in range(m + n):\n",
    "                if high.next: high = high.next \n",
    "                else: \n",
    "                    low.next = None\n",
    "                    return head\n",
    "            low.next = high \n",
    "            low = high\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        cur = head  \n",
    "        while cur:\n",
    "            for i in range(m-1):\n",
    "                if cur:\n",
    "                    cur = cur.next \n",
    "                else:\n",
    "                    return head   \n",
    "            if cur:\n",
    "                kk = cur.next \n",
    "            else:\n",
    "                return head \n",
    "            for j in range(n):\n",
    "                if kk:\n",
    "                    kk = kk.next \n",
    "                else:\n",
    "                    cur.next = kk \n",
    "                    return head   \n",
    "            cur.next = kk\n",
    "            cur = kk \n",
    "        return head \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if not head: return None\n",
    "        a = b = head\n",
    "        c, d = m, n\n",
    "        while m-1 and a.next:\n",
    "            a, b = a.next, b.next\n",
    "            m -=1\n",
    "        while n and b.next:\n",
    "            b = b.next\n",
    "            n-=1\n",
    "        a.next = self.deleteNodes(b.next, c, d)\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        left, right = head, head\n",
    "        remain = 1\n",
    "        remove = 0\n",
    "        while left and right:\n",
    "            if remain < m:\n",
    "                left = left.next\n",
    "                right = right.next\n",
    "                remain += 1\n",
    "            else:\n",
    "                remain = 0\n",
    "                while remove <= n and right:\n",
    "                    right = right.next\n",
    "                    remove += 1\n",
    "                left.next = right\n",
    "                remove = 1\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if head is None:\n",
    "            return head\n",
    "\n",
    "        cur = head\n",
    "        while cur is not None:\n",
    "            m_count = 1\n",
    "            while cur is not None and m_count < m:\n",
    "                cur = cur.next\n",
    "                m_count += 1\n",
    "            \n",
    "            cur_head = cur\n",
    "            if cur_head is None:\n",
    "                break\n",
    "            \n",
    "            n_count = 0\n",
    "            while cur is not None and n_count < n:\n",
    "                cur = cur.next\n",
    "                n_count += 1\n",
    "            \n",
    "            cur_head.next = cur.next if cur is not None else None\n",
    "            cur = cur_head.next\n",
    "            \n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        current = head\n",
    "        previous = head\n",
    "        save_count = 0\n",
    "        remove_count = 0\n",
    "        while current is not None:\n",
    "            if save_count < m:\n",
    "                save_count += 1\n",
    "                previous = current\n",
    "                current = current.next\n",
    "            elif remove_count < n:\n",
    "                remove_count += 1\n",
    "                current = current.next\n",
    "            elif remove_count == n:\n",
    "                previous.next = current\n",
    "                save_count = 0\n",
    "                remove_count = 0\n",
    "        if save_count == m and remove_count == n:\n",
    "            previous.next = current\n",
    "        if remove_count > 0 and remove_count < n:\n",
    "            previous.next = current\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        dummy = ListNode(-1)\n",
    "        p = dummy\n",
    "        q = head\n",
    "        while q:\n",
    "            for _ in range(m):\n",
    "                if q:\n",
    "                    p.next = q\n",
    "                    p = p.next\n",
    "                    q = q.next\n",
    "                else:\n",
    "                    return dummy.next\n",
    "            p.next = None\n",
    "            for _ in range(n):\n",
    "                if q:\n",
    "                    q = q.next\n",
    "                else:\n",
    "                    return dummy.next\n",
    "        return dummy.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        fast = slow = head\n",
    "        while True:\n",
    "            for _ in range(m-1):\n",
    "                if slow.next:\n",
    "                    slow = slow.next\n",
    "                else:\n",
    "                    return head\n",
    "            \n",
    "            for _ in range(m+n):\n",
    "                if fast.next:\n",
    "                    fast = fast.next\n",
    "                else:\n",
    "                    slow.next = None\n",
    "                    return head\n",
    "\n",
    "            slow.next = fast\n",
    "            slow = fast\n",
    "            \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        p = ListNode(0)\n",
    "        p.next = head\n",
    "        while p.next:\n",
    "            r = m\n",
    "            while p.next and r:\n",
    "                print(p.val, r)\n",
    "                p = p.next\n",
    "                r -= 1\n",
    "            q = p.next\n",
    "            t = n\n",
    "            while q and t:\n",
    "                q = q.next\n",
    "                t -= 1\n",
    "            p.next = q\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        current = head\n",
    "        lis = []\n",
    "        while current:\n",
    "            for i in range(m + n):\n",
    "                try:\n",
    "                    if i > -1 and i < m:\n",
    "                        lis.append(current.val)\n",
    "                        current = current.next\n",
    "                        continue\n",
    "                except:\n",
    "                    break\n",
    "                try:\n",
    "                    if i >= m and i < n + m:\n",
    "                        current = current.next\n",
    "                except:\n",
    "                    break\n",
    "        new_head = ListNode(0)  # 新链表的头节点\n",
    "        node = new_head\n",
    "        for val in lis:\n",
    "            node.next = ListNode(val)\n",
    "            node = node.next\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        current = head\n",
    "        lis = []\n",
    "        while current:\n",
    "            for i in range(m + n):\n",
    "                try:\n",
    "                    if i > -1 and i < m:\n",
    "                        lis.append(current.val)\n",
    "                        current = current.next\n",
    "                        continue\n",
    "                except:\n",
    "                    break\n",
    "                try:\n",
    "                    if i >= m and i < n + m:\n",
    "                        current = current.next\n",
    "                except:\n",
    "                    break\n",
    "        new_head = ListNode(0)  # 新链表的头节点\n",
    "        node = new_head\n",
    "        for val in lis:\n",
    "            node.next = ListNode(val)\n",
    "            node = node.next\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:\n",
    "        current = head\n",
    "        lis = []\n",
    "        while current:\n",
    "            for i in range(m + n):\n",
    "                try:\n",
    "                    if i > -1 and i < m:\n",
    "                        lis.append(current.val)\n",
    "                        current = current.next\n",
    "                        continue\n",
    "                except:break\n",
    "                \n",
    "                try:\n",
    "                    if i >= m and i < n + m:\n",
    "                        current = current.next\n",
    "                except:\n",
    "                    break\n",
    "        new_head = ListNode(0)  # 新链表的头节点\n",
    "        node = new_head\n",
    "        for val in lis:\n",
    "            node.next = ListNode(val)\n",
    "            node = node.next\n",
    "        return new_head.next"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
